package topcoder;

public class DropCoins {

	public int getMinimum(String[] board, int K){
		int r = _getMinimum(board, K, 0);
		if(r == Integer.MAX_VALUE)
			return -1;
		else
			return (int)r;
	}
	
	public int _getMinimum(String[] board, int K, int a){
		if(count(board) == K)
			return 0;
		if(count(board) < K)
			return Integer.MAX_VALUE;
		
		int c1 = Integer.MAX_VALUE,c2 = Integer.MAX_VALUE,c3 = Integer.MAX_VALUE,c4 = Integer.MAX_VALUE;
		if(a != 2)
			c1 = _getMinimum(up(board), K, 1);
		if(a != 1)
			c2 = _getMinimum(down(board), K, 2);
		if(a != 4)
			c3 = _getMinimum(left(board), K, 3);
		if(a != 3)
			c4 = _getMinimum(right(board), K, 4);
		
		int r = Math.min(Math.min(c1,c2), Math.min(c3,c4));
		
		if(r == Integer.MAX_VALUE)
			return Integer.MAX_VALUE;
		else
			return r + 1;
	}
	
	private int count(String[] board){
		int c = 0;
		for(int i = 0; i < board.length; i++){
			for(int j = 0; j < board[0].length(); j++){
				if(board[i].charAt(j) == 'o')
					c++;
			}
		}
		return c;
	}
	
	private String[] up(String[] board){
		String[] b = board.clone();
		for(int i = 0; i < board.length; i++){
			StringBuilder builder = new StringBuilder(b[i]);
			for(int j = 0; j < board[0].length(); j++){
				if(i < board.length - 1)
					builder.setCharAt(j, b[i+1].charAt(j));
				else
					builder.setCharAt(j, '.');
			}
			b[i] = builder.toString();
		}	
		return b;
	}
	
	private String[] down(String[] board){
		String[] b = board.clone();
		for(int i = board.length - 1; i >= 0; i--){
			StringBuilder builder = new StringBuilder(b[i]);
			for(int j = 0; j < board[0].length(); j++){
				if(i > 0)
					builder.setCharAt(j, b[i-1].charAt(j));
				else
					builder.setCharAt(j, '.');
			}
			b[i] = builder.toString();
		}	
		return b;
	}
	
	private String[] left(String[] board){
		String[] b = board.clone();
		for(int i = 0; i < board.length; i++){
			StringBuilder builder = new StringBuilder(b[i]);
			for(int j = 0; j < board[0].length(); j++){
				if(j < board.length - 1)
					builder.setCharAt(j, b[i].charAt(j+1));
				else
					builder.setCharAt(j, '.');
			}
			b[i] = builder.toString();
		}	
		return b;
	}
	
	private String[] right(String[] board){
		String[] b = board.clone();
		for(int i = 0; i < board.length; i++){
			StringBuilder builder = new StringBuilder(b[i]);
			for(int j = board[0].length() - 1; j >= 0; j--){
				if(j > 0)
					builder.setCharAt(j, b[i].charAt(j-1));
				else
					builder.setCharAt(j, '.');
			}
			b[i] = builder.toString();
		}	
		return b;
	}
	
	public static void main(String[] args) {
		DropCoins dc = new DropCoins();
		String[] board = {"...."
				,".oo."
				,".oo."
				,"...."};
		
		dc.getMinimum(board, 3);
	}
}
